package Prim;

import java.util.Arrays;

public class PrimDemo {
    public static void main(String[] args) {
        char[] data = new char[]{'A','B','C','D','E','F','G'};
        int verxs = data.length;
        int[][] weight = new int[][]{
                {10000,5,7,10000,10000,10000,2},
                {5,10000,10000,9,10000,10000,3},
                {7,10000,10000,10000,8,10000,10000},
                {10000,9,10000,10000,10000,4,10000},
                {10000,10000,8,10000,10000,5,4},
                {10000,10000,10000,4,5,10000,6},
                {2,3,10000,10000,4,6,10000},};
        MGraph graph = new MGraph(verxs);
        MinTree minTree = new MinTree();
        minTree.creatGraph(graph,verxs,data,weight);
        minTree.showGraph(graph);
        minTree.prim(graph,1);
    }
}

//创建最小生成树
class MinTree{
    /**
     * 创建如
     * @param graph:所生成的图
     * @param verxs:图中的节点数
     * @param data:图中节点的值
     * @param weight:图中两节点之间的权重
     */
    public void creatGraph(MGraph graph, int verxs, char[] data, int[][] weight){
        for(int i = 0; i < verxs; i++){
            graph.data[i] = data[i];
            for(int j = 0; j < verxs; j++){
                graph.weight[i][j] = weight[i][j];
            }
        }
    }

    /**
     * 显示图的邻接矩阵
     * @param graph:目标图
     */
    public void showGraph(MGraph graph){
        for(int[] link : graph.weight){
            System.out.println(Arrays.toString(link));
        }
    }

    /**
     * prim算法
     * @param graph:目标图
     * @param v：表示第几个顶点
     */
    public void prim(MGraph graph, int v){
        //visited表示目标节点是否被访问过
        int[] visited = new int[graph.verxs];
        visited[v] = 1;
        int minWeight = 10000;
        //h1，h2表示找到的顶点下标
        int h1 = -1;
        int h2 = -1;

        //k大循环表示遍历所有的边
        for(int k = 1; k < graph.verxs; k++){
            for(int i = 0; i < graph.verxs; i++){
                for(int j = 0; j < graph.verxs; j++){
                    //visited[i] == 1表示第一个顶点已被访问过
                    //visited[j] == 0表示邻接顶点未被访问过
                    if(visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight){
                        minWeight = graph.weight[i][j];
                        h1 = i;
                        h2 = j;
                    }
                }
            }
            System.out.println("边<" + graph.data[h1] + "," + graph.data[h2] + ">,权值：" + minWeight);
            //将邻接顶点设置为已访问过
            visited[h2] = 1;
            minWeight = 10000;
        }
    }
}

//创建图
class MGraph{
    //图中节点个数
    int verxs;
    //节点值
    char[] data;
    //节点间权值
    int[][] weight;

    public MGraph(int verxs) {
        this.verxs = verxs;
        data = new char[verxs];
        weight = new int[verxs][verxs];
    }
}


